1. Field of the Invention
The present invention relates to a method for generating a pseudorandom noise sequence with an arbitrarily designated phase, which is applied to a communication system using a spread-modulation method.
2. Description of the Related Art
In a communications system using spread spectrum modulation, the spectra of many signals can be spread over a broadband, multiplexed, and transmitted by using a Code Division Multiple Access (CDMA). FIG. 1 shows one principle of the configuration of a CDMA communication system.
On a CDMA transmitter 901 side, a spread-modulation unit 905 spread-spectrum modulates the transmission signal which is output from a transmission signal source 903, for example, which is frequency-modulated or phase-modulated by using the spread code generated by a spread code generating unit 904, and the resultant transmission signal is transmitted to a transmission line 906.
On a CDMA receiver 902 side, a despread-demodulation unit 908 must despread (demodulate) a reception signal by using the despread code which has the same sequence and phase as those of the spread code on the transmitter side and which is output from a despread code generating unit 907 in synchronization with the timing of the transmitter side.
Accordingly, the despread code generating unit 907 must have the capability for generating a sequence code having an arbitrary phase according to a timing synchronization signal (normally, this signal is autonomously generated from a reception signal within the CDMA receiver 902).
In a CDMA communication, the spread code (and the despread code) for spreading a spectrum must satisfy the following conditions in addition to the condition that the spread code must be a broadband signal: (1) the number of types of spread codes must be large in order to allow codes to be assigned to many users; (2) a cross-correlation must be small in order to allow the spread code to be identified from a different user code; (3) a self-correlation must be strictly identified in order to ensure the synchronization with the signal addressed to a local station; and (4) the spread code must be as random as possible, have a long cycle, and be difficult to be decoded in order to improve the confidentiality of a communication signal.
Conventionally, a PN (Pseudorandom Noise) sequence is known as the code for satisfying such conditions.
Since the PN sequence can be generated by using a shift register, its generation process is not really random but deterministic. However, the PN sequence is a code having the following properties of randomness. Therefore, this is suitable as the spread code of the CDMA communication, which requires the above described conditions.
Property 1: Balance Property
The numbers of times that xe2x80x9c1xe2x80x9d and xe2x80x9c0xe2x80x9d respectively appear in one cycle of the sequence are, different only by 1.
Property 2: Run Property
In the runs of xe2x80x9c1sxe2x80x9d and runs of xe2x80x9c0sxe2x80x9d which are included in one cycle, the length of each run is xe2x80x9c1xe2x80x9d when a classification number of that run is xc2xd, xe2x80x9c2xe2x80x9d when a classification number of that run is xc2xc, xe2x80x9c3xe2x80x9d when a classification number of that run is xe2x85x9, . . . . That is, there is a number of {(classification number of run)xc3x97(xc2xd k)} of the runs which have the run number k. Note that, for the runs of which this number is less than 1, these runs become meaningless runs.
Property 3: Correlation Property
If sequences are made cyclic and a comparison is made between the respective code values of the corresponding digits of the two sequences in every state, the number of the digits whose code values match and that of the digits whose code values do not match are different only by 1.
An M sequence (maximum length sequence) is known as a typical PN sequence satisfying such properties. The M sequence is generated using the circuit including an n-stage shift register, which is shown in FIG. 2.
In FIG. 2, the respective outputs of the stages of the n-stage shift register are multiplied with a coefficient fi (0 or 1), and the multiplication results are fed back to the input side of the shift register via exclusive-OR circuits (+signs encircled in this figure).
If the coefficient fi satisfies a particular condition when the values of all of the stages of the shift register are not xe2x80x9c0xe2x80x9d in an initial state, the cycle of the sequence ai output from the shift register will become the maximum cycle (2nxe2x88x921) that the n-stage shift register can generate. Such a sequence is referred to as an M sequence.
The circuit shown in FIG. 2 can be represented by the following equation.                                           ∑                          j              =              0                        n                    ⁢                                    f              j                        ⁢                          a                              i                +                j                                                    =        0                            (        1        )            
If fn=1 is assigned to this equation, the following equation can be obtained.                               a                      i            +            n                          =                              ∑                          j              =              0                                      n              -              1                                ⁢                                    f              j                        ⁢                          a                              i                +                j                                                                        (        2        )            
The above described equations (1) and (2) are referred to as linear recurring equations. Here, if a delay operator x which satisfies ai+1=xjai is assigned, the equation (2) becomes as follows.                                           (                                          ∑                                  j                  =                  0                                n                            ⁢                                                f                  j                                ⁢                                  x                  j                                                      )                    ⁢                      xe2x80x83                    ⁢                      a            i                          =        0                            (        3        )            
The polynomial f(x) of the following equation, which is represented by the term on the left side of the above equation (3), is referred to as a characteristic polynomial.                               f          ⁡                      (            x            )                          =                              ∑                          j              =              0                        n                    ⁢                                    f              j                        ⁢                          x              j                        ⁢                          xe2x80x83                        ⁢                          (                                                                    f                    0                                    ≠                  0                                ,                                  xe2x80x83                                ⁢                                                      f                    n                                    =                  1                                            )                                                          (        4        )            
If the coefficient fj included in this equation (4) belongs to a Galois field GF (2), and if f(x) is the minimal polynomial possessed by a primitive element xcex1 of the Galois field GF (2n), it is known that the circuit shown in FIG. 2, which includes the n-stage shift register, can generate the M sequence having the maximum cycle (2nxe2x88x921). This minimal polynomial is referred to as a primitive polynomial of degree k. Its details are referred to, for example, in the document xe2x80x9cSensing/Recognition Series Vol. 8, M Sequence and its Application, pp. 16-xe2x80x9d, written by J. Kashiwagi and published by Shokodo.
The primitive polynomial can be calculated as described on pp. 171 to 191 of this document, and many types of primitive polynomials were previously obtained in some of the papers cited in this document.
For example, the coefficient fj, which is included in the equation (4) and corresponds to a primitive polynomial f(x)=x4+x+1 of the Galois field GF (24), becomes f0=1, f1=1, f2=f3=0, and f4=1. As a result, the M sequence generating circuit shown in FIG. 3 can be configured based on the circuit shown in FIG. 2.
Here, an M sequence xdai whose phase is shifted by d bits from the output ai of the M sequence will be obtained. If a predetermined initial state of the n-stage (4 stages in FIG. 3) shift register is provided, all of the states of the M sequence, which succeed the initial state, are determined. Therefore, the M sequence having an arbitrary phase is proved to be obtained with the linear combination of the outputs of the respective stages of the shift register, as represented by the following equation (5).
xdai=b0x0ai+b1x1ai+b2x2ai+ . . . +bnxe2x88x921xnxe2x88x921aixe2x80x83xe2x80x83(5)
Consequently, the circuit for generating the M sequence having an arbitrary phase can be configured from the M sequence generating circuit shown in FIG. 3, which includes the 4-stage shift register, as shown in FIG. 4.
In FIG. 4, an initial value is assigned to each of the stages of the 4-stage shift register (SR) 1203 in a PN generator (PNG) 1201. The feedback equivalent to that shown in FIG. 3 is provided by a TAP 1204. TAP information (TAPINFO) 1205, which corresponds to the respective coefficients b0 through b3 included in the equation (5), is provided to 4 AND circuits (ANDs) 1206 in a variable tap (ATAP) 1202. Consequently, the output selected according to the TAPINFO 1205 from among the outputs of the respective stages of the SR 1203 is added to another output by the corresponding AND circuit (AND) 1206 and exclusive-OR circuit (EXOR) 1207, whereby the M sequence xdai having an arbitrary phase d is output as the result of the addition.
The means for providing the initial value to the SR 1203, the means for providing the clock for implementing a shift operation, etc. are omitted and are not shown in FIG. 4.
Provided next is the explanation about the principle for calculating the coefficients b0 through b3, which are included in the equation (5) and form the TAPINFO 1205.
In the PNG 1201 shown in FIG. 4, the M sequences x1ai to x3ai, whose phases are respectively shifted by 1 to 3 bits from the output ai of the M sequence are the outputs themselves of the shift register stages SR1 through SR4 in the second to fourth stages, as shown in FIG. 5.                                                                             the output
shifted by 1 bit                            ⁢                              xe2x80x83                            ⁢                              x                1                            ⁢                              a                i                            ⁢                              :                            ⁢                              xe2x80x83                            ⁢                              b                1                                      =            1                    ,                      xe2x80x83                    ⁢                                    b              0                        =                                          b                2                            =                                                b                  3                                =                0                                                    ⁢                  
                ⁢                                                                 the output
shifted by 2 bits                            ⁢                              xe2x80x83                            ⁢                              x                2                            ⁢                              a                i                            ⁢                              :                            ⁢                              xe2x80x83                            ⁢                              b                2                                      =            1                    ,                      xe2x80x83                    ⁢                                    b              0                        =                                          b                1                            =                                                b                  3                                =                0                                                    ⁢                  
                ⁢                                                                 the output
shifted by 3 bits                            ⁢                              xe2x80x83                            ⁢                              x                3                            ⁢                              a                i                            ⁢                              :                            ⁢                              xe2x80x83                            ⁢                              b                3                                      =            1                    ,                      xe2x80x83                    ⁢                                    b              0                        =                                          b                1                            =                                                b                  2                                =                0                                                                        (        6        )            
Next, the M sequence x4ai, whose phase is shifted by 4 bits from the output ai of the M sequence will be considered. In this case, if the primitive polynomial f(x)=x4+x+1 is set
f(x)=x4+x+1=0xe2x80x83xe2x80x83(7)
the following equations are satisfied with the operation in the Galois field.
x4=1+xxe2x80x83xe2x80x83(8)
x4ai=x0ai+x1aixe2x80x83xe2x80x83(9)
According to the above described equation (9), the M sequence x4ai whose phase is shifted by 4 bits from the output ai of the M sequence, is proved to be represented by the exclusive-OR operation performed between the output ai and the output x1ai whose phase is shifted by 1 bit. That is, the M sequence x4ai whose phase is shifted by 4 bits from the output ai can be obtained with the exclusive-OR operation performed between the output of the first shift register stage SR0 and that of the second shift register stage SR1, as shown in FIG. 6. Namely                                                              the output
shifted by 4 bits                        ⁢                          xe2x80x83                        ⁢                          x              4                        ⁢                          a              i                        ⁢                          :                        ⁢                          xe2x80x83                        ⁢                          b              0                                =                                    b              1                        =            1                          ,                  xe2x80x83                ⁢                              b            2                    =                                    b              3                        =            0                                              (        10        )            
Then, the M sequence x5ai whose phase is shifted by 5 bits from the output ai of the M sequence can be obtained with the exclusive-OR operation performed between the output of the second shift register stage SR1 and that of the third shift register stage SR2 according to following equation (11) obtained by multiplying both sides of the equation (9) by x, as shown in FIG. 6.
xe2x80x83x5ai=x1ai+x2aixe2x80x83xe2x80x83(11)
Namely,                                                              the output
shifted by 5 bits                        ⁢                          xe2x80x83                        ⁢                          x              5                        ⁢                          a              i                        ⁢                          :                        ⁢                          xe2x80x83                        ⁢                          b              1                                =                                    b              2                        =            1                          ,                  xe2x80x83                ⁢                              b            0                    =                                    b              3                        =            0                                              (        12        )            
Furthermore, the M sequence x6ai whose phase is shifted by 6 bits from the output ai of the M sequence can be obtained with the exclusive-OR operation performed between the output of the third shift register stage SR2 and that of the fourth shift register stage SR3 according to the following equation (13) obtained by multiplying both Asides of the equation (11) by x.
x6ai=x2ai+x3aixe2x80x83xe2x80x83(13)
Namely,                                                              the output
shifted by 6 bits                        ⁢                          xe2x80x83                        ⁢                          x              6                        ⁢                          a              i                        ⁢                          :                        ⁢                          xe2x80x83                        ⁢                          b              2                                =                                    b              3                        =            1                          ,                  xe2x80x83                ⁢                              b            0                    =                                    b              1                        =            0                                              (        14        )            
The configuration shown in FIG. 7 is conventionally known as the configuration for sequentially outputting the coefficients b0 through b3, which form the TAPINFO 1205, according to the above described rules.
In this configuration, a 4-stage shift register (SR) 1501 is used in correspondence with the primitive polynomial f(x)=x4+x+1, and an exclusive-OR circuit EXOR 1502 is inserted between the outside of the shift register stage a0 and the input side of the shift register stage a1, which respectively correspond to the terms 1=x0 and x=x1 forming the right side of the equation (7). The output of the output stage a3 of the shift register (corresponding to the term x4 on the left side of the equation (7)) is fed back to the EXOR 1502. Since the stage preceding the shift register stage a0 does not exist, the output of the output stage a3 is directly fed back to the input side of the shift register stage a0.
More typically, a shift register with the number of stages corresponding to the degree of the primitive polynomial f(x) is used. Similar to the equation (7), an equation is formed by setting f(x) to xe2x80x9c0xe2x80x9d so that the term of the highest degree is included on the left side and the terms of other degrees are included on the right side. Then, an exclusive-OR circuit is inserted into the input side of thee shift register stage corresponding to each of the terms forming the right side of the formed equation, and the output (corresponding to each of the terms on the left side of the equation) of an output stage of the shift register is fed back to the exclusive-OR circuit.
Next, xe2x80x9c1xe2x80x9d is assigned to the first shift register stage a0 as the initial value of the SR 1501, while xe2x80x9c0xe2x80x9d is assigned to the remaining shift register stages a1 through a3 shown in FIG. 7.
The shift operation is then performed the number of times which corresponds to a desired amount of phase shift, so that the respective coefficients b0 through b3 forming the TAPINFO 1205 shown in FIG. 4 are determined as the respective outputs of the stages a0 through a3 of the SR 1501.
With the conventional method shown in FIG. 7, however, the shift operation must be performed the number of times which corresponds to a desired amount of phase shift in order to calculate the TAPINFO 1205 corresponding to the desired amount of phase shift. Therefore, if the cycle of the M sequence becomes longer (for example, 10 minutes or so), it requires a huge amount of time to calculate the TAPINFO 1205.
The present invention was developed in the above described background, and aims at quick calculation of each piece of tap information corresponding to each amount of phase shift.
The present invention assumes the technique for calculating the respective phase shift coefficients b0 through bnxe2x88x921 intended for obtaining the M sequence xdai whose phase is shifted by d bits from the output ai of the M sequence generated with a primitive polynomial f(x) of degree n, by using a linear combination
b0x0ai+b1x1ai+b2x2ai+ . . . +bnxe2x88x921xnxe2x88x921ai
of the respective M sequences x0ai through xnxe2x88x921ai whose phases are shifted by 0 to nxe2x88x921 bits from the output ai.
In a first step of the present invention, the binary value of the amount of phase shift d is input.
In a second step, the n-bit vector value corresponding to a decimal value xe2x80x9c1xe2x80x9d is set as an initial input vector value.
In a third step, a target bit is set as the most significant bit of the binary value of the amount of phase shift d input in the first step.
In a fourth step, the vector; value of the primitive element xcex1 is multiplied with the input vector value within the Galois field GF (2n) and the result of the multiplication is defined as an output vector value if the value of the target bit is xe2x80x9c1xe2x80x9d, and the input vector value is defined as the output vector value unchanged if the value of the target bit is xe2x80x9c0xe2x80x9d.
In a fifth step, a square operation is performed for the output vector value obtained in the fourth step within the Galois field GF (2n).
In a sixth step, the position of the target bit is shifted to the least significant bit side by 1 bit in the binary value of the amount of phase shift d input in the first step, and the result of the square operation performed in the fifth step is used as a newly input vector value, with which the fourth and fifth steps are performed.
In a seventh step, the respective elements of the operation results obtained so far are output as the phase shift coefficients b0 through bnxe2x88x921 when the fourth and fifth steps have been performed for all of the bits structuring the binary value of the amount of phase shift d input in the first step.
According to the present invention, phase shift coefficients can be calculated simply by repeatedly performing the operation for multiplying a current vector value with the vector representation value of the primitive element xcex1 and squaring the result of the vector multiplication, or the operation for squaring the unchanged current vector value, an approximate number of flog(d)/log(2)) times.
These two types of operations within the Galois field GF (2n) can be implemented by hardware of a compact size.
In this way, as the cycle of an M sequence becomes longer, the number of repetition times that the phase shift coefficients of the M sequence are calculated can be significantly reduced compared with that of the conventional method.